package someTestExcemple.huaweiOd.slidingWindow;

//华为OD机试 - 宽度最小的子矩阵 - 滑动窗口（Java 2025 A卷 200分）
//https://blog.csdn.net/guorui_java/article/details/146897974
import java.util.*;
public class            MatrixOfMinimumWidth {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入矩阵的行数和列数
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 定义矩阵，存储所有数字
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        // 输入要求数组的长度 K
        int k = sc.nextInt();
        int[] reqArr = new int[k];
        for (int i = 0; i < k; i++) {
            reqArr[i] = sc.nextInt();
        }

        // 构造要求数字的频率字典（需要的数量） 数字-频率
        Map<Integer, Integer> need = new HashMap<>();
        for (int num : reqArr) {
            need.put(num, need.getOrDefault(num, 0) + 1);
        }

        // 预处理：统计每一列中各数字的出现频率，存入 colFreq 数组
        // colFreq[j] 表示第 j 列的数字及其出现次数
        List<Map<Integer, Integer>> colFreq = new ArrayList<>();
        for (int j = 0; j < m; j++) {
            Map<Integer, Integer> freq = new HashMap<>();
            for (int i = 0; i < n; i++) {
                int cur = matrix[i][j];
                freq.put(cur, freq.getOrDefault(cur, 0) + 1);
            }
            colFreq.add(freq);
        }

        // 使用滑动窗口在列上寻找最小宽度
        int left = 0;
        int ans = Integer.MAX_VALUE;
        Map<Integer, Integer> window = new HashMap<>();

        // 从左到右遍历所有列
        for (int right = 0; right < m; right++) {
            // 将当前右边界列的频率加到窗口中
            for (Map.Entry<Integer, Integer> entry : colFreq.get(right).entrySet()) {
                int key = entry.getKey();
                int value = entry.getValue();
                window.put(key, window.getOrDefault(key, 0) + value);
            }

            // 当窗口内满足所有需要的数字及数量时，尝试缩小窗口
            while (check(window, need)) {
                // 更新答案为当前窗口的宽度
                //这一步要先做
                ans = Math.min(ans, right - left + 1);
                //尝试缩小左边界
                // 将左边界列的频率从窗口中移除
                for (Map.Entry<Integer, Integer> entry : colFreq.get(left).entrySet()) {
                    int key = entry.getKey();
                    int value = entry.getValue();
                    window.put(key, window.get(key) - value);
                }
                left++;  // 缩小窗口
            }
        }

        // 如果未找到满足要求的子矩阵，则输出 -1，否则输出最小宽度
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
    // 检查窗口内的频率是否满足要求的频率
    private static boolean check(Map<Integer, Integer> window, Map<Integer, Integer> need) {
        for (Map.Entry<Integer, Integer> entry : need.entrySet()) {
            int key = entry.getKey();
            int count = entry.getValue();
            if (window.getOrDefault(key, 0) < count) {
                return false;
            }
        }
        return true;
    }
}
